public class RBT {

    // 判断指向这个节点的连接是否是红色，约定空连接为黑色
    public boolean isRed(Node node){
        if(node == null){
            return false;
        }
        return node.color;
    }

    // 左旋，将红色的右链接转换为红色的左链接
    // 其实只是将用两个键中的较小者作为根节点变换成使用较大者作为根节点。
    public Node rotateLeft(Node node){
        Node root = node.right;
        node.right = root.left;
        root.left = node;
        root.color = node.color;
        node.color = true;    // 红色
        return root;
    }

    // 右旋，将红色的左链接转换为红色的右链接
    // 其实只是将用两个键中的较大者作为根节点变换成使用较小者作为根节点。
    public Node rotateRight(Node node){
        Node root = node.left;
        node.left = root.right;
        root.right = node;
        root.color = node.color;
        node.color = true;
        return root;
    }


    // 颜色转换，将根节点的链接颜色变成红色，它的左右孩子的链接均变成黑色
    // 用于处理这个节点的左右孩子节点的链接都是红色的情况
    public void flipColors(Node node){
        node.color = true;
        node.left.color = false;
        node.right.color = false;
    }


    // 向一个红黑树中插入一个节点，root为树的根节点
    public Node insert(Node root, int val){
        root = myInsert(root,val);
        root.color = false;
        return root;
    }
    // 递归插入
    public Node myInsert(Node root, int val){
        if(root == null){                         // 标准的插入操作，和父节点用红色链接相连
            return new Node(val,true);
        }
        if(root.val < val){
            root.right = myInsert(root.right,val);    // 右侧插入
        }else if(root.val > val){
            root.left = myInsert(root.left,val);     // 左侧插入
        }else{
            return root;           // 说明这个节点值已经存在，不再进行插入
        }
        // 下面就要分情况进行调整
        if( !isRed(root.left) && isRed(root.right)){       // 右子节点的链接为红色，左节点链接为黑色
            root = rotateLeft(root);      // 左旋
        }
        if(isRed(root.left) && isRed(root.left.left)){     // 左节点以及左节点的左节点均为红色
            root = rotateRight(root);     // 右旋
        }
        if(isRed(root.left) && isRed(root.right)) {        // 左右节点链接均为红色
            flipColors(root);             // 颜色翻转
        }
        return root;
    }









}
